默写

1 数组向右移动K位
思路： 全部反转，  反转前k位 (k%n)  反转后k位

public void reverse(int[] nums,in k){
    int len = nums.length;
    k=k%n
    reverse(nums,0,len-1);
    reverse(nums,0,k-1);
    reverse(nums,k,len-1);
}

private reverse(int nums ,int i,int k){
    while( i < k ){
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
        i++;
        k--;
    }
}

2.堆排序

/**
     * 创建堆，
     * @param arr 待排序列
     */
    private static void heapSort(int[] arr) {
        //创建堆
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }

        for(int i = arr.length - 1; i > 0; i--){
            //将堆顶元素与末尾元素进行交换 
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //重新对堆进行调整
            adjustHeap(arr, 0, i);
        }
    }


    /**
     * 调整堆
     * @param arr 待排序列
     * @param parent 父节点
     * @param length 待排序列尾元素索引
     */
private static void adjustHeap(int[] arr, int parent, int length) {
        //将temp作为父节点
        int temp = arr[parent];
        //左孩子
        int lChild = 2 * parent + 1;

        while (lChild < length) {
            //右孩子
            int rChild = lChild + 1;
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (rChild < length && arr[lChild] < arr[rChild]) {
                lChild++;
            }

            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= arr[lChild]) {
                break;
            }

            // 把孩子结点的值赋给父结点
            arr[parent] = arr[lChild];

            //选取孩子结点的左孩子结点,继续向下筛选
            parent = lChild;
            lChild = 2 * lChild + 1;
        }
        arr[parent] = temp;
    }

-搞定动态规划和思路分解题，核心记住递推表达式和题目步骤。
  --思路和实现分开。
    --实现记住关键点
    --常见操作熟练

-第二步，超级熟练默写基本题，然后模拟考试提取知识。


动态规划










0-1背包
问能否能装满背包(或者最多装多少):dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
对应题目如下:
    动态规划:416.分割等和子集 
    给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
    总和sum，两个子集相当，其中一个子集总和sum/2;
        背包的体积为sum / 2
        背包要放入的商品(集合里的元素)重量为 元素的数值 ，价值也为元素的数值 
        背包如何正好装满，说明找到了总和为 sum / 2 的子集。 
        背包中每一个元素是不可重复放入。
    动态规划:1049.最后一块石头的重量 II
    尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小

问装满背包有几种方法:dp[j] += dp[j - nums[i]] 
对应题目如下:
    动态规划:494.目标和
    给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意 一个整数，你都可以从 + 或 - 中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
        本题要如何使表达式结果为target，
        既然为target，那么就一定有 left组合 - right组合 = target。
        left + right等于sum，而sum是固定的。
            公式来了， left - (sum - left) = target -> left = (target + sum)/2 。 
            target是固定的，sum是固定的，left就可以求出来。
        此时问题就是在集合nums中找出和为left的组合。  
        此时问题就转化为，装满容量为x背包，有几种方法。  



   
问背包装满最大价值:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 
对应题目如下: 
    动态规划:474.一和零





  

    状态压缩 ，一维也可以
-----------------------------------------------
